//给你两棵二叉树： root1 和 root2 。 
//
// 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠
//，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。 
//
// 返回合并后的二叉树。 
//
// 注意: 合并过程必须从两个树的根节点开始。 
//
// 
//
// 示例 1： 
//
// 
//输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
//输出：[3,4,5,5,4,null,7]
// 
//
// 示例 2： 
//
// 
//输入：root1 = [1], root2 = [1,2]
//输出：[2,2]
// 
//
// 
//
// 提示： 
//
// 
// 两棵树中的节点数目在范围 [0, 2000] 内 
// -10⁴ <= Node.val <= 10⁴ 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 961 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution617 {
    /**
     * 这里额定义了一颗新树，也可以直接在原树上进行修改
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        queue.offer(root1);
        queue.offer(root2);
        TreeNode root = new TreeNode(root1.val+ root2.val);
        // 此时左右都不为空
        treeNodeQueue.offer(root);
        while (!queue.isEmpty()) {
            root1 = queue.poll();
            root2 = queue.poll();
            TreeNode node = treeNodeQueue.poll();
            if(root1.left != null && root2.left != null){
                queue.offer(root1.left);
                queue.offer(root2.left);
                node.left = new TreeNode(root1.left.val+root2.left.val);
                treeNodeQueue.offer(node.left);
            }
            if(root2.right != null && root1.right != null){
                queue.offer(root1.right);
                queue.offer(root2.right);
                node.right = new TreeNode(root1.right.val+root2.right.val);
                treeNodeQueue.offer(node.right);
            }
            if(root1.left == null || root2.left ==null){
                node.left = root1.left == null ? root2.left : root1.left;
            }
            if(root1.right == null || root2.right == null){
                node.right = root1.right == null ? root2.right : root1.right;
            }
        }
        return root;
    }
    /**
     * 错误版本，root一直变化
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees4(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        queue.offer(root1);
        queue.offer(root2);
        TreeNode root = null;
        // 此时左右都不为空
        treeNodeQueue.offer(new TreeNode(root1.val+ root2.val));
        while (!queue.isEmpty()) {
            root1 = queue.poll();
            root2 = queue.poll();
            root = treeNodeQueue.poll();  //这样写root会一直变化！！！！！
            if(root1.left != null && root2.left != null){
                queue.offer(root1.left);
                queue.offer(root2.left);
                root.left = new TreeNode(root1.left.val+root2.left.val);
                treeNodeQueue.offer(root.left);
            }
            if(root2.right != null && root1.right != null){
                queue.offer(root1.right);
                queue.offer(root2.right);
                root.right = new TreeNode(root1.right.val+root2.right.val);
                treeNodeQueue.offer(root.right);
            }
            if(root1.left == null || root2.left ==null){
                root.left = root1.left == null ? root2.left : root1.left;
            }
            if(root1.right == null || root2.right == null){
                root.right = root1.right == null ? root2.right : root1.right;
            }
        }
        return root;
    }
    public TreeNode mergeTrees3(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root2.right, root2.right);
        return root1;
    }
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2; //这里返回的是root2节点，包括root2节点下面的所有节点
        if(root2 == null) return root1;
        TreeNode root = new TreeNode(root1.val+ root2.val);
        root.left = mergeTrees2(root1.left, root2.left);
        root.right = mergeTrees2(root1.right, root2.right);
        return root;
    }



    public static void main(String[] args) {
        Integer[] arr1 = {3,4,5,1,2};
        Integer[] arr2 = {4,1,2,1};
        TreeNode root1 = BinaryTreeFactory.generateBinaryTreeFromArray(arr1);
        TreeNode root2 = BinaryTreeFactory.generateBinaryTreeFromArray(arr2);
        Solution617 solution = new Solution617();
        TreeNode treeNode = solution.mergeTrees(root1, root2);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
